package com.markus.code.排序.base;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/4 17:56
 * todo: 插入排序
 */
public class InsertSort {
    public static void insertSort(int arr[]){
        if (arr == null || arr.length == 0){
            return ;
        }
        /**
         * 插入排序维护的是[0~i)是有序的，将i元素往前移动，直到遇到比它小的数字停止移动
         */
        for (int i=0 ; i<arr.length ; i++){
            int index = i;
            int value = arr[i];
            while(index > 0 && value < arr[index-1]){
                arr[index] = arr[index-1];
                index --;
            }
            arr[index] = value;
        }
    }
    public static void main(String[] args) {
        int []arr = {3,4,2,5,7,6};
        insertSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}
